The present disclosure relates to hash table systems and methods, and more specifically to hash table systems and methods that use multiple hash table banks.
Hash tables are often used in place of conventional indexes to store and retrieve electronically stored information because the hash tables are much faster and are less resource intensive. Hash tables are generally more efficient than search trees or any other table lookup structure. For this reason, they are widely used in many kinds of computer software, particularly for associative arrays, database indexing, caches, and sets. Most hash table designs assume that hash collisions—different keys that map to the same hash value—will occur and must be accommodated in some way.
A hash table is made up of two parts: an array (the actual table where the data to be searched is stored) and a mapping function, known as a hash function. The hash function is a mapping from the input space to the integer space that defines the indices of the array. In other words, the hash function provides a way for assigning numbers to the input data such that the data can then be stored at the array index corresponding to the assigned number. There is always the chance that two inputs will hash to the same output. This indicates that both elements should be inserted at the same place in the array, and this is impossible. This phenomenon is known as a collision.